import java.util.*;

/**
 * Implementation of Dijkstra's algorithm
 */
public class Dijkstra
{
    private static final int MAX_MINUTES_DIFFERENCE = 60;
    /**
     * Compute all the paths from the given source node.
     * This method must be called before getting the shortest
     * path.
     * @param source The source location/node
     */
    public static void computeAllPaths(HashMap<String, Location> graph, Location source, Calendar startTime)
    {
        //For each location in the graph, we must reset!
        ArrayList<Location> locations = new ArrayList<Location>(graph.values());
        Iterator<Location> allLocationIter = locations.iterator();
        while (allLocationIter.hasNext())
        {
            Location currentLocation = allLocationIter.next();
            currentLocation.setMinDistance(32768);
            currentLocation.setPreviousService(null);
            currentLocation.setLatestTime(null);
            currentLocation.setPreviousEdge(null);
            currentLocation.setPrevious(null);
        }
        //OK, all locations in the map are now reset.
        source.setMinDistance(0);
        PriorityQueue<Location> queue = new PriorityQueue<Location>();
        queue.addAll(graph.values());
        
        Calendar currentTime = (Calendar) startTime.clone();
        
        //System.out.println("Start time: " + Service.calendarToString(startTime) + "Date: " + Service.calendarToDateString(startTime));
        
        //The last time used
        //Run whilst something still in the queue
        while (!queue.isEmpty())
        {
            //System.out.println("Queue is not empty");
            Location u = queue.remove();
            
            if (u.getMinDistance() == 32768)
                break;
            
            if (u.getLatestTime() != null)
            {
                //System.out.println("current time: " + Service.calendarToString(currentTime));
                currentTime = u.getLatestTime();
            }

            //Added
            //For each edge from this location
            Iterator<Edge> edgeIter = u.getOutlist().iterator();
            while (edgeIter.hasNext())
            {

                //System.out.println("In edge iterator");
                Edge current = edgeIter.next();
                
                if (u.getLatestTime() == null)
                {
                    currentTime = current.getStartTime();
                    //System.out.println("Current time: " + Service.calendarToString(currentTime));
                    Calendar boundLower = (Calendar)startTime.clone();
                    boundLower.set(Calendar.HOUR_OF_DAY, (boundLower.get(Calendar.HOUR_OF_DAY) - 1));
                    Calendar boundHigher = (Calendar)startTime.clone();
                    boundHigher.set(Calendar.HOUR_OF_DAY, (boundHigher.get(Calendar.HOUR_OF_DAY) + 1));

                    if (currentTime.before(boundLower) || currentTime.after(boundHigher))
                    {
                        /*boolean firstCheck = currentTime.before(boundLower);
                        boolean secondCheck = currentTime.after(boundHigher);
                        System.out.println("\n------------------");
                        System.out.println("First check: " + firstCheck + " second: " + secondCheck);
                        System.out.println("Bound lower: " + Service.calendarToString(boundLower) + "\t" + Service.calendarToDateString(boundLower));
                        System.out.println("Bound upper: " + Service.calendarToString(boundHigher) + "\t" + Service.calendarToDateString(boundHigher));
                        System.out.println("Failing with: " + Service.calendarToString(currentTime) + "\t" + Service.calendarToDateString(currentTime));
                        System.out.println("------------------\n");*/
                        continue;
                    }
                    u.setLatestTime(currentTime);
                }
                //The next time
                Calendar nextTime = (Calendar) currentTime.clone();
                nextTime.add(Calendar.MINUTE, current.getDuration());
                
                //If the service is in the past, don't use it
                if (nextTime.before(nextTime))
                    continue;
                //System.out.println("Current service: " + current.getService());
                Location v = current.getEndLocation();
                //System.out.println("V location: " + v.getStopName());
                double weight = current.getDuration();
                double weightOfU = u.getMinDistance() + weight;
                
                //System.out.println("U Location: " + u.getStopName() + "Weight of u: " + weightOfU + " min distance: " + u.getMinDistance());

                if (weightOfU < v.getMinDistance())
                {
                    queue.remove(v);
                    v.setMinDistance(weightOfU);
                    //System.out.println("Setting min distance to: " + v.getMinDistance());
                    v.setPrevious(u);
                    v.setPreviousService(current.getService());
                    //System.out.println("Setting previous location to: " + u.getStopName());
                    //System.out.println("Setting previous edge as: " + current.getEndLocation().getStopName());
                    v.setPreviousEdge(current);
                    v.setLatestTime(nextTime);
                    queue.add(v);
                }
            }
        }
        //System.out.println("Finished Dijkstra!");
    }

    /**
     * Get the shortest path from the source specified in
     * computeAllPaths.
     * @param target The node to try and reach
     * @return A List representing each location to travel through
     */
    public static ArrayList<Location> getShortestPath(Location target)
    {
        
        ArrayList<Location> returnList = new ArrayList<Location>();
        
        for (Location location = target; location != null; location = location.getPrevious())
        {
            returnList.add(location);
        }

        Collections.reverse(returnList);

        return returnList;
    }

}
